﻿#include<iostream>

using namespace std;
/*
自底向上的推出矩阵连乘的最优解
先从两个矩阵相乘开始，而后三个矩阵相乘，四个......直到推出目标长度的最优解 ，即假设一个矩阵链，初始长度为2，算出所有相邻矩阵相乘的计算次数，而后使其长度为3...4...直到目标长度
状态转移方程：
 m[i][j]=min {m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}   i<=k<j  i<j
 m[i][j]=0   i==j;
*/
#define LEN 5  //矩阵个数 
//矩阵连乘函数，找到最优解 
void MatrixChain(int *p, int m[][LEN + 1], int s[][LEN + 1]) {
	for (int i = 0; i < LEN + 1; i++)	m[i][i] = 0;  	//初始化，对角线元素置零，即当矩阵链长度为1时（只有一个矩阵）不用乘，为零 
	for (int r = 2; r <= LEN; r++) {  //r表示矩阵链的长度，从2开始,两个矩阵相乘，而后3...4...5... 
		for (int i = 1; i <= LEN - r + 1; i++) {	//i是矩阵链的首个矩阵，小于矩阵个数减矩阵链长度加一 
			int j = i + r - 1;	//j是矩阵链的最后一个元素 
			m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];   //m[i][j]是子结构，从最左边开始推 
			s[i][j] = i;  //标记断开的位置 
			for (int k = i + 1; k < j; k++) {	//k是i和j直接的断开点，是在i和j之间的子结构 ，通过k的循环找到最优的解 
				int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];   //状态转移方程 
				if (t < m[i][j]) {
					m[i][j] = t;	//更新最优解 
					s[i][j] = k;	//更新断开点 
				}
			}
		}
	}
}

//回溯函数，根据s[i][j]数组标记的位置，回溯找到断开的位置 
void Traceback(int i, int j, int s[][LEN + 1]) {
	if (i == j) {	//当i与j相等 说明回溯到该矩阵的位置了
		cout << "A" << i;
	}
	else {
		cout << "(";
		Traceback(i, s[i][j], s);	//从尾往头回溯
		Traceback(s[i][j] + 1, j, s);	//从断点往后回溯
		cout << ")";
	}
}
//输出函数 
void output(int t[][LEN + 1]) {
	for (int i = 1; i <= LEN; i++) {
		for (int j = 1; j <= LEN; j++) {
			cout << " " << t[i][j] << " ";
		}
		cout << endl;
	}
}
int main(void) {
	int p[LEN + 1] = { 6,8,9,3,4,10 }; //矩阵的维度分别是2*3,3*4,4*5,5*6,6*7，LEN+1个数表示LEN个矩阵 
	int m[LEN + 1][LEN + 1] = { 0 };	//记录最优子结构的二维数组 
	int s[LEN + 1][LEN + 1] = { 0 };	//记录最优解对应的括号的位置 	

	MatrixChain(p, m, s);

	cout << endl;
	output(m);
	cout << endl;
	output(s);
	cout << endl;
	cout << "outcome:" <<endl;
	Traceback(1, LEN, s);
	cout << endl;

	return 0;
}